#include<bits/stdc++.h>
#define maxn 100000+5
using namespace std;
long long mostBig[maxn*20];
long long read() {
	long long x;
	scanf("%lld",&x);
	return x;
}
long long IN() {
	long long a=0;
	char ch;
	while((ch=getchar())!=' '&&ch!='\n') {
		a*=10;
		a+=ch-'0';
	}
	return a;
}
long long a[maxn];
long long qry(long long o,long long L,long long R,long long l,long long r) {
	long long ans=-0x3f3f3f3f;
	long long mid=(L+R)>>1;
	if(l<=L&&r>=R) return mostBig[o];
	if(mid>=l) ans=max(ans,qry(o*2,L,mid,l,r));
	if(mid<r) ans=max(ans,qry(o*2+1,mid+1,R,l,r));
	return ans;
}
void upd(long long o,long long L,long long R,long long x,long long y) {
	a[x]=y;
	long long mid=(L+R)/2;
	if(L==R)mostBig[o]=y;
	else {
		if(x<=mid)upd(o*2,L,mid,x,y);
		else upd(o*2+1,mid+1,R,x,y);
		mostBig[o]=max(mostBig[o*2],mostBig[o*2+1]);
	}
}
void build(long long o,long long L,long long R) {
	long long mid=(L+R)/2;
	if(L==R) mostBig[o]=a[L];
	else {
		build(o*2,L,mid);
		build(o*2+1,mid+1,R);
		mostBig[o]=max(mostBig[o*2],mostBig[o*2+1]);
	}
}
signed main() {
	long long n=read(),m=read();
	for(long long i=1; i<=maxn; i++) mostBig[i]=0x3f3f3f3f;
	memset(a,0,sizeof(a));
	for(long long i=1; i<=n; i++) a[i]=read();
	build(1,1,n);
	for(int i=0;i<m;i++) {
		long long k=read(),x=read(),y=read();
		if(k==1) upd(1,1,n,x,a[x]+y);
		else printf("%lld\n",qry(1,1,n,x,y));
	}
}#include<bits/stdc++.h>
#define maxn 100000+5
using namespace std;
long long mostBig[maxn*20];
long long read() {
	long long x;
	scanf("%lld",&x);
	return x;
}
long long IN() {
	long long a=0;
	char ch;
	while((ch=getchar())!=' '&&ch!='\n') {
		a*=10;
		a+=ch-'0';
	}
	return a;
}
long long a[maxn];
long long qry(long long o,long long L,long long R,long long l,long long r) {
	long long ans=-0x3f3f3f3f;
	long long mid=(L+R)>>1;
	if(l<=L&&r>=R) return mostBig[o];
	if(mid>=l) ans=max(ans,qry(o*2,L,mid,l,r));
	if(mid<r) ans=max(ans,qry(o*2+1,mid+1,R,l,r));
	return ans;
}
void upd(long long o,long long L,long long R,long long x,long long y) {
	a[x]=y;
	long long mid=(L+R)/2;
	if(L==R)mostBig[o]=y;
	else {
		if(x<=mid)upd(o*2,L,mid,x,y);
		else upd(o*2+1,mid+1,R,x,y);
		mostBig[o]=max(mostBig[o*2],mostBig[o*2+1]);
	}
}
void build(long long o,long long L,long long R) {
	long long mid=(L+R)/2;
	if(L==R) mostBig[o]=a[L];
	else {
		build(o*2,L,mid);
		build(o*2+1,mid+1,R);
		mostBig[o]=max(mostBig[o*2],mostBig[o*2+1]);
	}
}
signed main() {
	long long n=read(),m=read();
	for(long long i=1; i<=maxn; i++) mostBig[i]=0x3f3f3f3f;
	memset(a,0,sizeof(a));
	for(long long i=1; i<=n; i++) a[i]=read();
	build(1,1,n);
	for(int i=0;i<m;i++) {
		long long k=read(),x=read(),y=read();
		if(k==1) upd(1,1,n,x,a[x]+y);
		else printf("%lld\n",qry(1,1,n,x,y));
	}
}